/*
Date:20210422 9:22am
key:关于所有的跳格子方法次数问题可以做一个总结。
    对于每个dp[i],满足几种跳法的a[i]要求，就加上几种跳法。
    比如此题i>=2时一定满足两种跳法，故dp[i]=dp[i-1]+dp[i-2];
*/
class Solution {
public:
    int climbStairs(int n)
    {
        int*dp=new int[n];
        if(n==0){return 0;}
        if(n==1){return 1;}
        if(n==2){return 2;}
        dp[0]=1;
        dp[1]=2;
        for(int i=2;i<n;i++)
        {
            {
                
                dp[i]=dp[i-1]+dp[i-2];
            }
        }
        return dp[n-1];
    }
};